package binary_search_tree

type tBSTreeIterator struct {
	tree *tBinarySearchTree
	queue *tVisitQueue
	version uint64
}


type tVisitQueue struct {
	head *tQueuedNode
	tail *tQueuedNode
}

type tQueuedNode struct {
	node *tBinaryNode
	next *tQueuedNode
}

func newQueuedNode(node *tBinaryNode) *tQueuedNode {
	return &tQueuedNode{
		node: node,
		next: nil,
	}
}

func newVisitQeuue() *tVisitQueue {
	return &tVisitQueue{
		nil,
		nil,
	}
}

func (me *tVisitQueue) push(node *tBinaryNode) {
	if node == nil {
		return
	}

	qn := newQueuedNode(node)
	if me.head == nil {
		me.head = qn
		me.tail = qn
	} else {
		me.tail.next = qn
		me.tail = qn
	}
}

func (me *tVisitQueue) poll() (bool, *tBinaryNode) {
	if me.head == nil {
		return false, nil

	} else {
		it := me.head
		if it == me.tail {
			me.tail = nil
		}
		me.head = me.head.next
		return true, it.node
	}
}

func (me *tVisitQueue) more() bool {
	return me.head != nil
}

func newBSTreeIterator(tree *tBinarySearchTree) IIterator {
	it := &tBSTreeIterator{
		tree: tree,
		queue: newVisitQeuue(),
		version: tree.version,
	}
	it.queue.push(tree.root)
	return it
}

func (me *tBSTreeIterator) More() bool {
	if me.version != me.tree.version {
		return false
	} else {
		return me.queue.more()
	}
}

func (me *tBSTreeIterator) Next() (bool, interface{}) {
	if !me.More() {
		return false, nil
	}

	ok, node := me.queue.poll()
	if !ok {
		return false, nil
	}

	me.queue.push(node.left)
	me.queue.push(node.right)
	return true, node.value
}